#include <deque>
#include <list>
#include <numeric>
#include <set>
#include <time.h>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <iostream>
#include <algorithm>
int const kMinSize = 1000;
int const kMaxSize = 8000;

int *data = new int[kMaxSize];
void consume(int, ...)
{
}

void generate_data()
{
    for(int k = 0; k != kMaxSize; ++k)
        data[k] = rand();
}
//for c array
int* c_array = new int[kMaxSize];
void c_array_fill(int size)
{
    delete[] c_array;
    c_array = new int[size];
    for(int k = 0; k != size; ++k)
        c_array[k] = data[k];
}
void c_array_traverse(int size)
{
    int sum = 0;
    for(int k = 0; k != size; ++k)
        sum += c_array[k];
    consume(0, sum);
}
void c_array_lookup(int size)
{
    int const desired_value = data[size/2];
    int k;
    for( k = 0; k != size; ++k)
        if(c_array[k] == desired_value)
            break;
    consume(0,k);
}
//for vector<int>

std::vector<int>* std_vector = new std::vector<int>;
void vector_fill(int size)
{
    delete std_vector;
    std_vector = new std::vector<int>;
    for(int k = 0; k != size; ++k)
        std_vector->push_back(data[k]);
}
void vector_traverse(int)
{
    consume(0, std::accumulate(std_vector->begin(),
                               std_vector->end(),0));
}
void vector_lookup(int size)
{
    std::find(std_vector->begin(),std_vector->end(),data[size/2]);
    consume(0,0);
}

//for deque

std::deque<int>* std_deque = new std::deque<int>;
void deque_fill(int size)
{
    delete std_deque;
    std_deque = new std::deque<int>;
    for(int k = 0; k != size; ++k)
        std_deque->push_back(data[k]);
}
void deque_traverse(int)
{
     std::accumulate(std_deque->begin(),
                               std_deque->end(),0);
     consume(0,0);

}
void deque_lookup(int size)
{
    std::find(std_deque->begin(),
                         std_deque->end(),
                         data[size/2]);
    consume(0,0);
}
//for list
std::list<int>* std_list = new std::list<int>;

void list_fill(int size)
{
    delete std_list;
    std_list = new std::list<int>;
    for(int k = 0; k != size; ++k)
        std_list->push_back(data[k]);
}
void list_traverse(int)
{
     std::accumulate(std_list->begin(),
                     std_list->end(),0);
     consume(0,0);
     
}
void list_lookup(int size)
{
    std::find(std_list->begin(),
                         std_list->end(),
                         data[size/2]);
    consume(0, 0);

}
//for set
std::set<int>* std_set = new std::set<int>;
void set_fill(int size)
{
    delete std_set;
    std_set = new std::set<int>;
    for(int k = 0; k != size; ++k)
        std_set->insert(data[k]);
}
void set_traverse(int)
{
    consume(0,
            std::accumulate(std_set->begin(),
                               std_set->end(),0));
}
void set_lookup(int size)
{
     std_set->find(data[size/2]);
     consume(0, 0);
}

//common drirver
void print_header()
{
    std::cout << "Container kind    size insertion   traverse lookup"
              << std::endl;
}
typedef void (*Test)(int);

int calibrate(int seconds, Test test, int size)
{
    clock_t end = clock() + seconds*CLOCKS_PER_SEC;
    int n;
    for( n = 0; clock() < end; ++n)
        test(size);
    return n;
}
double time_in_seconds(int n, Test test, int size)
{
    clock_t start = clock();
    for(int k = 0; k != n; ++k){
        test(size);
    }
    return (clock() - start)/double(CLOCKS_PER_SEC);
}

void benchmark(char const* container_name, int n,
               Test filling, Test traverse, Test lookup)
{
    for(int size = kMinSize; size <= kMaxSize; size*=2){
        filling(size);
        printf("%13s   %7d: %7.2f  %7.2f %7.2f\n",
               size == kMinSize ? container_name:"", size,
               time_in_seconds(n, filling, size),
               time_in_seconds(n, traverse, size),
               time_in_seconds(n, lookup, size));
    }
    printf("\n");
}

int main()
{
    generate_data();
    c_array_fill(kMinSize);
    int n = calibrate(1, &c_array_lookup, kMinSize);

    print_header();
    benchmark("C array", n,
      c_array_fill, c_array_traverse, c_array_lookup);
    benchmark("Std::vector",n,
              vector_fill, vector_traverse, vector_lookup);
    benchmark("std::deque", n,
              deque_fill, deque_traverse, deque_lookup);
    benchmark("std::list", n,
              list_fill, list_traverse, list_lookup);
    benchmark("std::set", n,
              set_fill, set_traverse, set_lookup);
    return 0;
}

            
